package offer.day32;

public class No54KthNode {
    /*
     * 面试题54：二叉搜索树的第K大节点
     * 题目：给定一个二叉搜索树，请找出其中第K大的节点。
     * 例如：在5->(left)3   5->(right)7 的二叉搜索树中，
     * 			3->(left)2    3->(right)4
     * 			7->(left)6	  7->(right)8
     * 按节点数值大小排序，第三大节点的值是4
     *
     *
     * 思路：使用中序遍历二叉树的方法，进行遍历。
     * {2，3，4，5，6，7，8}则将其以递增的形式输出，则此数组中第3个就是要找的
     *
     *
     * */
    public static void main(String[] args) {
        No54KthNode k = new No54KthNode();
        BinaryTreeNode head = new BinaryTreeNode(5);
        BinaryTreeNode one = new BinaryTreeNode(3);
        BinaryTreeNode two = new BinaryTreeNode(7);
        BinaryTreeNode three = new BinaryTreeNode(2);
        BinaryTreeNode four = new BinaryTreeNode(4);
        BinaryTreeNode five = new BinaryTreeNode(6);
        BinaryTreeNode six = new BinaryTreeNode(8);

        head.left = one;
        head.right = two;
        one.left = three;
        one.right = four;
        two.left = five;
        two.right = six;
        three.left = null;
        three.right = null;
        four.left = null;
        four.right = null;
        five.left = null;
        five.right = null;
        six.left = null;
        six.right = null;

        int index = 3;
        System.out.println("按照节点数值大小进行排序，数组中第"+index+"大节点的值是："+k.GetKthNode(head,index).val);
    }

    int count=0;
    private BinaryTreeNode GetKthNode(BinaryTreeNode head, int index) {
        if(head==null||index<=0){
            return null;
        }
        BinaryTreeNode node=GetKthNode(head.left,index);
        if(node!=null){
            return node;
        }
        count++;
        if(count==index){
            return head;
        }
        node=GetKthNode(head.right,index);
        if(node!=null){
            return node;
        }
        return null;
    }
}
